﻿using System.Diagnostics;

namespace DataStructure;

public class LinkListStack<E>:IStack<E>
{
    //链表作为底层数据结构存储元素
    private LinkList<E> list;

    //构造函数初始化链表
    public LinkListStack()
    {
        list = new LinkList<E>();
    }

    //获取栈中元素个数 O（1）
    public int Count => list.Count;

    //判断栈是否为空 O（1）
    public bool IsEmpty => list.IsEmpty;

    //查看栈顶元素 O（1）
    public E peek()
    {
        return list.First;
    }

    //删除栈顶元素 O（1）
    public E pop()
    {
        return list.RemoveFirst();
    }

    //往栈顶添加元素 O（1）
    public void Push(E e)
    {
        list.AddFirst(e);
    }

    public void Clear()
    {
        list.Clear();
    }

    //打印链表栈信息
    public override string ToString()
    {
        return "Stack: top " + list.ToString();
    }
}

class LinkListStack
{
    static void Main(string[] args)
    {
        /*
        LinkListStack<int> stack = new();
        for (int i = 0; i < 5; i++)
        {
            stack.Push(i);
            Console.WriteLine(stack);
        }

        stack.pop();
        Console.WriteLine(stack);

        Console.Read();           
        */

        ///*
        //测试不同底层实现的栈性能
        //SeqListStack和LinkListStack耗时消耗巨大
        //由于链表的实现需要不断的new空间，所以内存操作耗时较大。
        //而对于数组操作，是对连续空间进行操作的，C#底层对连续空间的访问有非常好的优化。
        //再加上数据规模增大以后，动态数组resize调用的频次其实很小，所以得到这个测试结果是正常的：）
        int N = 20000000;

        SeqListStack<int> seqListStack = new(N);
        long t1 = TestStack(seqListStack, N);
        Console.WriteLine("SeqListStack'time: " + t1 + "ms");

        LinkListStack<int> linkListStack = new();
        long t2 = TestStack(linkListStack, N);
        Console.WriteLine("LinkListStack'time: " + t2 + "ms");

        //C#提供的栈是基于数组实现的。
        Stack<int> stack = new Stack<int>(N);
        Stopwatch t = new Stopwatch();
        t.Start();

        for (int i = 0; i < N; i++)
            stack.Push(i);
        for (int i = 0; i < N; i++)
            stack.Pop();
        
        t.Stop();
        Console.WriteLine("Stack'time: " + t.ElapsedMilliseconds + "ms");

        Console.Read();
        //*/
    }

    //对栈执行N次入栈和出栈操作
    //对于TestStack方法，不管是测试数组栈还是链表栈它们的时间复杂度都是O（n）
    //运行时间和数据规模成正比的关系
    static long TestStack(IStack<int> stack, int n)
    {
        Stopwatch t = new Stopwatch();
        t.Start();

        for (int i = 0; i < n; i++)
            stack.Push(i);
        for (int i = 0; i < n; i++)
            stack.pop();

        t.Stop();
        return t.ElapsedMilliseconds;
    }
}
